Steps:

1. pick up the next item in the list
2. look at all the previous elements in the list, and move it to the appropriate position
3. repeat until we've done all the items

e.g. for [12, 6, 21, 5, 9]

1. we start with 12. There are no previous elements, so we move onto the next item.
2. We look at 6. Comparing it to the only previous element 6 we can see that we want to move it before 12, so our list should look like [6, 12, 21, 5, 9].
3. We look at 21, and compare it to the previous elements. First we compare 21 and 12 – clearly 21 is greater than 12 (and we know that the previous elements must all be sorted, so we can stop there).
4. We look at 5. 5 is smaller than 21, so we compare it to the previous element. 5 is also smaller than 12 so we turn to look at 6. 5 is less than 6. Therefore our list is now [5, 6, 12, 21, 9]
5. We now look at 9. 9 is less than 21, so we look at 12. 9 is less than 12, so we look at 6. 9 is greater than 6, so we insert 9 after 6. Our list is now [5, 6, 9, 12, 21]

The final list is therefore [5, 6, 9, 12, 21].

further reading

• Have a look at this animation of an insertion sort